package com.xinwei.leetcode.数组;



import java.util.*;

// https://leetcode-cn.com/problems/combination-sum/

// 个人总结：这道题和46题全排列回溯最大的区别就在于本身可重复，怎么在可重复使用元素的同时，保证答案的不重复是这道题的难点
public class _39_组合总和 {
    static List<List<Integer>> lists = new ArrayList<>();

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        Deque<Integer> deque = new LinkedList<>();
        dfs(candidates, target, deque, 0);
        return lists;
    }

    private static void dfs(int[] candidates, int remain, Deque<Integer> deque, int start) {
        if (remain == 0) {
            // 刚好加起来就等于目标值，把栈中的列表保存
            lists.add(new ArrayList<>(deque));
            return;
        }

        if (remain > 0 && remain < candidates[start] || remain < 0) { // 只有前面排过序次才能只判断start位置
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            deque.push(candidates[i]);
            dfs(candidates, remain - candidates[i], deque, i);
            deque.pop();
        }
    }
}
